/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30/FONT#10=ZERO30/FONT#11=BAXI30/FONT#12=MS25



␈↓ ↓H␈↓Random␈α
Remarks␈α
on␈α"Can␈α
programming␈α
be␈αliberated␈α
from␈α
the␈αvon␈α
Neumann␈α
style?␈α A␈α
functional
␈↓ ↓H␈↓style and its algebra of programs" by John Backus

␈↓ ↓H␈↓␈↓ α_1.␈α∂It␈α∂isn't␈α∂clear␈α∂to␈α∂me␈α∂that␈α∞functional␈α∂programming␈α∂per␈α∂se␈α∂solves␈α∂the␈α∂bottleneck␈α∞problem.
␈↓ ↓H␈↓That is solved by parallelism, which can be done either functionally or in sequential notation.

␈↓ ↓H␈↓␈↓ α_2.␈α↔It␈α↔further␈α↔seems␈α↔to␈α↔me␈α↔that␈α↔simple␈α↔sequential␈α↔programming␈α↔with␈α↔just␈α⊗variables
␈↓ ↓H␈↓assignments␈α⊂and␈α⊂␈↓αgo to␈↓s␈α⊂has␈α⊂one␈α⊃important␈α⊂virtue.␈α⊂ Namely␈α⊂is␈α⊂no␈α⊂information␈α⊃hidden␈α⊂between
␈↓ ↓H␈↓statements,␈α∞although␈α
the␈α∞values␈α
of␈α∞subexpressions␈α
are␈α∞hidden␈α
within␈α∞statements.␈α
 It␈α∞seems␈α∞to␈α
me
␈↓ ↓H␈↓that␈α∃languages␈α∀having␈α∃this␈α∃property␈α∀will␈α∃remain␈α∀important␈α∃at␈α∃least␈α∀for␈α∃some␈α∃theories.␈α∀ In
␈↓ ↓H␈↓particular,␈α∃they␈α⊗will␈α∃be␈α∃necessary␈α⊗for␈α∃some␈α⊗kinds␈α∃of␈α∃description␈α⊗of␈α∃hardware,␈α⊗because␈α∃all
␈↓ ↓H␈↓information preserved in a computing system has to be somewhere at all times.

␈↓ ↓H␈↓␈↓ α_3.␈α
Reduction␈α
semantics␈α
has␈α∞some␈α
disadvantages␈α
compared␈α
to␈α
model-theoretic␈α∞semantics.␈α
 It
␈↓ ↓H␈↓requires␈α
either␈α
non-denumerable␈αdomains␈α
of␈α
expressions,␈αe.g.␈α
expressions␈α
containing␈αarbitrary␈α
real
␈↓ ↓H␈↓numbers, or artificial restrictions to specific symbolic expression domains for numbers.

␈↓ ↓H␈↓␈↓ α_4.␈α
"Thirty␈α
year␈α
old"␈α
concept␈α
doesn't␈α
tell␈αus␈α
anything␈α
in␈α
itself.␈α
 No-one␈α
has␈α
modernized␈αthe
␈↓ ↓H␈↓integers␈α∂or␈α∞the␈α∂concept␈α∞of␈α∂four-wheeled␈α∞vehicle.␈α∂ In␈α∞fact,␈α∂the␈α∞idea␈α∂that␈α∞the␈α∂von␈α∂Neumann␈α∞style
␈↓ ↓H␈↓computer is out-of-date is at least 20 years old and so can be accused of being out-of-date itself.

␈↓ ↓H␈↓␈↓ α_5.␈α∂It␈α∞does␈α∂seem␈α∂plausible␈α∞that␈α∂the␈α∂von␈α∞Neumann␈α∂style,␈α∂(I␈α∞call␈α∂it␈α∂sequential␈α∞programming)
␈↓ ↓H␈↓creates␈α∂a␈α∂bottleneck,␈α⊂but␈α∂it␈α∂is␈α∂somewhat␈α⊂invidious␈α∂to␈α∂introduce␈α∂a␈α⊂technical␈α∂term␈α∂that␈α⊂implies␈α∂a
␈↓ ↓H␈↓personal␈α∩criticism␈α∩by␈α∩its␈α∩name.␈α∩ The␈α∩remark␈α∩taking␈α∩some␈α∩of␈α∩the␈α∩"blame"␈α∩wouldn't␈α∩solve␈α⊃the
␈↓ ↓H␈↓problem, unless the name were to be changed to "Backus bottleneck".

␈↓ ↓H␈↓␈↓ α_6.␈αp8.␈αI␈αagree␈αthat␈α
the␈αright␈αside␈αof␈αassignment␈αstatements␈α
is␈αa␈αmore␈αlogical␈αworld␈α
than␈αthe
␈↓ ↓H␈↓left.

␈↓ ↓H␈↓␈↓ α_7.␈α
It␈α
sure␈α
is␈α
true␈α
that␈α
pure␈α
LISP␈α
is␈αoften␈α
buried␈α
(p10),␈α
and␈α
I␈α
don't␈α
yet␈α
know␈α
whether␈α
it␈αis
␈↓ ↓H␈↓necessary or not.  It is certainly necessary with LISP in the shape it is.

␈↓ ↓H␈↓␈↓ α_8.␈α∞It␈α∞doesn't␈α∞seem␈α∞that␈α∞criticism␈α
that␈α∞␈↓↓n␈↓␈α∞is␈α∞in␈α∞the␈α∞program␈α
is␈α∞entirely␈α∞to␈α∞the␈α∞point.␈α∞ ␈↓↓n␈↓␈α∞is␈α
as
␈↓ ↓H␈↓changeable as anything else in the program.  g is to the point.

␈↓ ↓H␈↓␈↓ α_9.␈α∞I␈α∞am␈α∂dubious␈α∞about␈α∞the␈α∞inner␈α∂product␈α∞example␈α∞for␈α∞two␈α∂reasons:␈α∞First,␈α∞while␈α∂the␈α∞inner
␈↓ ↓H␈↓product␈αcan␈αbe␈αcomputed␈αin␈αthe␈αway␈αdescribed,␈αit␈αshouldn't␈αbe,␈αe.g.␈αnothing␈αshould␈αbe␈αtransposed.
␈↓ ↓H␈↓Second,␈α∞since␈α∂ corresponds␈α∞to␈α∞LISP␈α∂␈↓↓mapcar,␈↓␈α∞it␈α∞has␈α∂the␈α∞same␈α∞limitations,␈α∂and␈α∞won't␈α∂work␈α∞when
␈↓ ↓H␈↓␈↓↓maplist␈↓␈α
is␈αwanted,␈α
e.g.␈α
when␈αthe␈α
indices␈α
need␈αto␈α
be␈αtested.␈α
 Third,␈α
␈↓↓Insert␈↓␈αis␈α
a␈α
dubious␈αoperation,
␈↓ ↓H␈↓making␈αsense␈αonly␈α
when␈αthe␈αoperation␈αis␈α
associative.␈α Finally,␈αthe␈α
whole␈αdefinition␈αmakes␈αno␈α
sense
␈↓ ↓H␈↓for␈α∞zero␈α∞length␈α∞vectors,␈α∞while␈α∞the␈α∞Algol␈α∞60␈α∞definition␈α∞gives␈α∞the␈α∞right␈α∞answer␈α∞in␈α∞that␈α∞case.␈α∞ You
␈↓ ↓H␈↓can't␈α
get␈αout␈α
of␈αzero␈α
length␈αvectors␈α
if␈αyou␈α
want␈α
(as␈αBackus␈α
demands)␈αthat␈α
the␈αlength␈α
be␈αa␈α
variable.
␈↓ ↓H␈↓A variable may turn out to have the value zero.

␈↓ ↓H␈↓␈↓ α_10.␈α
In␈α
practice,␈α
a␈α
small␈α
framework␈α
and␈α
completely␈α
variable␈α
parts␈α
leads␈α
to␈αdifficulties,␈α
because
␈↓ ↓H␈↓the␈α⊃parts␈α⊂become␈α⊃implementation␈α⊂dependent␈α⊃or␈α⊂require␈α⊃manuals␈α⊂themselves.␈α⊃ In␈α⊃principle,␈α⊂the
␈↓ ↓H␈↓creators␈αof␈αparts␈αhave␈αthe␈αsame␈αobligation␈α
to␈αprovide␈αmanuals␈αas␈αthe␈αlanguage␈αdesigners,␈αbut␈α
they
␈↓ ↓H␈↓usually evade this responsibility.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ α_11. Damnit, let's call them Backus languages1)␈↓ α8

␈↓ ↓H␈↓12.␈αOne␈αsuspects␈αon␈αp17,␈αthat␈αthe␈αauthor␈αisn't␈αvery␈αfamiliar␈αwith␈αmuch␈αof␈αthe␈αliterature.␈α Anyway,
␈↓ ↓H␈↓the␈αpolemical␈αstyle␈αleads␈αme␈αto␈α
defend␈αsequential␈αprograms␈αeven␈αthough␈αI␈αalso␈α
prefer␈αapplicative
␈↓ ↓H␈↓systems.

␈↓ ↓H␈↓␈↓ α_13. At the bottom of p20, it looks like the camel has got his head back in the tent.

␈↓ ↓H␈↓␈↓ α_14.␈α∞On␈α∞p21,␈α∞criterion␈α
␈↓↓a␈↓␈α∞proposes␈α∞doing␈α∞without␈α
variables.␈α∞ Combinatory␈α∞logic␈α∞does␈α∞it,␈α
but
␈↓ ↓H␈↓the␈α
cost␈αin␈α
clarity␈αis␈α
too␈αgreat.␈α
 I␈αguess␈α
I␈αwould␈α
bet␈αthat␈α
variables␈αcan't␈α
be␈αdispensed␈α
with␈α
in␈αthe
␈↓ ↓H␈↓long run without making obscure programs.

␈↓ ↓H␈↓␈↓ α_15.␈αThe␈α
goal␈α(p21)␈α
of␈αa␈α
program␈αalgebra␈αis␈α
fine,␈αbut␈α
certain␈αstatements␈α
one␈αwants␈α
to␈αmake
␈↓ ↓H␈↓require more logic than just algebraic identities.

␈↓ ↓H␈↓␈↓ α_16.␈α
On␈α
p23␈α
Backus␈α
displays␈α
the␈α
common␈α
desire␈α
to␈α
restrict␈α
people␈α
for␈α
their␈α
own␈α
good.␈α
 ␈↓↓Sic
␈↓ ↓H␈↓↓semper tyranus␈↓.

␈↓ ↓H␈↓␈↓ α_17.␈αThe␈α
functional␈αforms␈αon␈α
p24␈αappear␈αto␈α
be␈αhigher␈αorder␈α
functions.␈α They␈α
are␈αconstants
␈↓ ↓H␈↓and␈αhave␈αnames.␈α First␈αlevel␈αfunctions␈αare␈αconstructed␈αfrom␈αbasic␈αfunctions␈αand␈αare␈αgiven␈αnames.
␈↓ ↓H␈↓The objects appear to have only limited capacity to be named.

␈↓ ↓H␈↓␈↓ α_18.␈αObjects␈αappear␈αon␈αp25␈αto␈αbe␈αLISP␈αtype␈αlists.␈α He␈αgives␈αup␈αunrestricted␈α␈↓↓cons.␈↓␈α Using␈αthe
␈↓ ↓H␈↓numbers as operators in this context is an improvement.  It was first suggested by Scott.

␈↓ ↓H␈↓␈↓ α_19.␈α∞Note␈α∞on␈α∞p26␈α∞that␈α∞while␈α∞the␈α∞language␈α∞has␈α∞no␈α∞variables,␈α∞it␈α∞has␈α∞been␈α∞convenient␈α∞to␈α∞use
␈↓ ↓H␈↓variables in making definitions.  The poor users cry, "Why can't we have variables too?".

␈↓ ↓H␈↓␈↓ α_20.␈α⊃On␈α⊃p26,␈α⊃he␈α⊃will␈α⊃be␈α⊃sorry␈α∩he␈α⊃said␈α⊃that␈α⊃the␈α⊃function␈α⊃symbols␈α⊃denoted␈α⊃by␈α∩sans␈α⊃serif
␈↓ ↓H␈↓numerals␈α∂are␈α∂different␈α∂from␈α∂the␈α∂serifed␈α∂numerals.␈α⊂ What␈α∂if␈α∂we␈α∂want␈α∂the␈α∂␈↓↓n␈↓th␈α∂element␈α∂of␈α⊂a␈α∂list
␈↓ ↓H␈↓where ␈↓↓n␈↓ is computed?

␈↓ ↓H␈↓␈↓ α_21.␈αThe␈αdefinitional␈αstyle␈αon␈αp26␈αis␈αconvenient.␈α It␈αdepends␈αon␈αthe␈αreader's␈αability␈αto␈αdecide
␈↓ ↓H␈↓that free variables are used in patterns that must be matched.  Will his users get some too?

␈↓ ↓H␈↓␈↓ α_22.␈α⊂On␈α⊂p27,␈α⊂␈↓↓reverse␈↓␈α⊂appears␈α⊂as␈α⊂a␈α⊂basic␈α⊂function.␈α⊂ If␈α⊂this␈α⊂is␈α⊂necessary␈α⊂or␈α⊂even␈α⊂especially
␈↓ ↓H␈↓convenient, something is rotten.

␈↓ ↓H␈↓␈↓ α_23.␈α∀The␈α∀logical␈α∀operators␈α∀are␈α∀taken␈α∪to␈α∀be␈α∀strict.␈α∀ He␈α∀never␈α∀said␈α∀whether␈α∪conditional
␈↓ ↓H␈↓expressions are strict.

␈↓ ↓H␈↓␈↓ α_24. ␈↓↓apndl␈↓ is ␈↓↓cons.  ␈↓

␈↓ ↓H␈↓25. Well, that's a lot more basic functions than LISP has.

␈↓ ↓H␈↓␈↓ α_26.␈αUsing␈α␈↓↓x␈↓␈αwith␈αa␈αbar␈αto␈αdenote␈αthe␈αconstant␈αfunction␈αmeans␈αthat␈αthe␈αconstant␈αmaker␈αitself
␈↓ ↓H␈↓cannot be composed.

␈↓ ↓H␈↓␈↓ α_27. A comparison with combinatory logic with its K and S combinators is called for.
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓␈↓ α_28.␈α
␈↓↓construction␈↓␈αis␈α
interesting,␈αbecause␈α
it␈α
is␈αnot␈α
a␈αsimple␈α
combinator.␈α
 It␈αdepends␈α
on␈αits␈α
object
␈↓ ↓H␈↓argument being a list of the right length and so is not in the spirit of combinatory logic.

␈↓ ↓H␈↓␈↓ α_29. On p29 it becomes clear that conditional expressions are not considered strict.

␈↓ ↓H␈↓␈↓ α_30.␈α␈↓↓insert␈↓␈αassociates␈αto␈αthe␈αright.␈α A␈αrecursive␈αdefinition␈αby␈αgum.␈α Why␈αcan't␈αthe␈αusers␈αhave
␈↓ ↓H␈↓them?  Most likely because they can't be trusted.

␈↓ ↓H␈↓␈↓ α_31. ␈↓↓binary to unary␈↓ looks ad hoc.  Why not ␈↓↓ternary to binary␈↓?

␈↓ ↓H␈↓␈↓ α_32.␈α∂␈↓↓while␈↓␈α∂allows␈α∂full␈α∂recursive␈α∂definition␈α∂but␈α∂of␈α∂the␈α∂iterative␈α∂kind␈α∂only.␈α∂ It␈α∂won't␈α∂give␈α∂␈↓↓n!␈↓
␈↓ ↓H␈↓directly, but I know he gets the recursive factorial late.

␈↓ ↓H␈↓␈↓ α_33.␈α∩On␈α∩p30␈α∩LISP␈α⊃type␈α∩recursive␈α∩definitions␈α∩are␈α⊃explicitly␈α∩introduced.␈α∩ Is␈α∩there␈α⊃mutual
␈↓ ↓H␈↓recursion␈αand␈α
is␈αthere␈α
a␈αway␈αof␈α
naming␈αrecursive␈α
functions␈αanalogous␈αto␈α
␈↓↓label.␈↓␈α If␈α
not␈αhe␈αcan't␈α
use
␈↓ ↓H␈↓them freely in his functional forms like  (␈↓↓mapcar).  ␈↓

␈↓ ↓H␈↓34.␈αThe␈αdefinition␈αof␈α␈↓↓well␈↓␈α␈↓↓formed␈↓␈αat␈αthe␈αbottom␈αof␈αp.30␈αhints␈αat␈αmutual␈αrecursion.␈α The␈αcondition
␈↓ ↓H␈↓is rather vague.  Well maybe not since only single symbols can appear on left sides.

␈↓ ↓H␈↓␈↓ α_35.␈αWith␈αFP␈α
completed␈αon␈αp31,␈α
I␈αwonder␈αhow␈αone␈α
writes␈αa␈αpolynomial␈α
such␈αas␈αλx.(x↑2␈α+␈α
2x
␈↓ ↓H␈↓+ 3)(x↑2 + 4).